class Solution {
    /**
        回溯+剪枝
    */
    List<Integer> list = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates,target,0);
        return ans;
    }
    public void dfs(int[] nums,int num,int index){
        if( num<=0 ){    // 剪枝1，如从index开始，只能把index之后的数字加入结果集
            if( num==0 ){
                ans.add(new ArrayList<>(list));
            }
            return ;
        }
        
        for(int i=index; i<nums.length; i++){
            if( num-nums[i]>=0 ){  // 剪枝2
                list.add(nums[i]);
                dfs(nums,num-nums[i],i);
                list.remove(list.size()-1);   
            }  
        }
    }
}